'''
https://leetcode.cn/problems/copy-list-with-random-pointer/description/
'''
from typing import Optional, Self

from c03_list.utils import ListNode


class Node:
    def __init__(self, x: int, next: Self | None = None, random: Self | None = None):
        self.val = int(x)
        self.next = next
        self.random = random
class Solution:
    def copyRandomList_forceSolution(self, head: Optional[Node]) -> Optional[Node]:
        cur = head
        dic = {}
        while cur:
            dic[cur] = Node(cur.val)
            cur = cur.next
        for k, v in dic.items():
            dic[k].next = dic[k.next] if k.next else None
            dic[k].random = dic[k.random] if k.random else None
        return dic[head] if head else None

    def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
        if not head: return None
        cur = head
        while cur:
            next = cur.next
            cur.next = Node(cur.val)
            cur.next.next = next
            cur = next
        cur = head
        while cur:
            cur.next.random = cur.random.next if cur.random else None
            cur = cur.next.next

        watch_dog = Node(-1)
        t = watch_dog
        cur = head
        while cur:
            copy = cur.next
            next = cur.next.next
            cur.next = next
            copy.next = next.next if next else None

            cur = next

            t.next = copy
            t = t.next
        return watch_dog.next